class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []

        def dfs(res, index, now, temp, max, len):
            if index == len:
                res.append("".join(temp))
                return
            if max > 0:
                temp.append('(')
                dfs(res, index + 1, now + 1, temp, max - 1, len)
                temp.pop()
            if now > 0:
                temp.append(')')
                dfs(res, index + 1, now - 1, temp, max, len)
                temp.pop()

        dfs(res, 0, 0, [], n, n*2)
        return res

